#pragma once

#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include "lex.hpp"

class Syn {
protected:
	std::string start;
	std::vector<std::string> symbols;
	std::unordered_set<std::string> VT;
	std::unordered_set<std::string> VN;
	std::vector<std::pair<std::string, std::vector<std::string>>> produce;				// 产生式
	std::unordered_map<std::string, bool> empty_map;									// 存储符号是否能推导出空字符
	std::unordered_map<std::string, std::unordered_set<std::string>> first_set;			// First集
	std::unordered_map<std::string, std::vector<int>> appears;							// 符号出现在哪些产生式右侧
	std::unordered_map<std::string, std::vector<std::string>> determine;				// 非终结符的Follow集决定哪些符号的Follow集
	std::unordered_map<std::string, std::unordered_set<std::string>> follow_set;		// Follow集
	std::unordered_map<std::string, std::vector<int>> lf_appears;						// 符号出现在哪些产生式左侧

	bool able_infer_to_empty(const std::string &);										// 判断符号能否推导出空字符
	std::unordered_set<std::string> get_first_set(const std::string &);
	std::unordered_set<std::string> get_follow_set(const std::string &);
	std::unordered_set<std::string> get_follow(std::string &);							// 获取某个符号当前能推导出的FOLLOW集
public:

	void read_rules(const char *);				// 从文件构建词法分析器
	void expand();								// 文法扩展，添加Start'=>Start
	void print_self();

	void infer_empty_map();						// 推导所有符号能否推导出空字符
	void print_empty_map();						// 打印各符号是否能推导出空字符
	void infer_first_set();						// 推导所有符号的FIRST集
	void print_first_set();						// 打印所有符号的FIRST集

	void get_appears();							// 得出符号出现在哪些产生式右侧
	void print_appears();
	void get_determine();						// 推导决定关系（反过来就是依赖关系）
	void print_determine();
	void infer_follow_set();					// 推导所有符号的FOLLOW集
	void print_follow_set();					// 打印所有符号的FOLLOW集
};

class LR: public Syn {
protected:
	std::vector<std::unordered_map<std::string, std::string>> predict;					// 预测分析表
public:
	class LRItem { // LR1项目
	public:
		std::string lf;
		std::vector<std::string> rh;
		std::string look_ahead;

		LRItem() {
			rh = std::vector<std::string>();
		}

		LRItem(const std::string &_lf, const std::vector<std::string> &_rh, const std::string &_look_ahead) {
			lf = _lf;
			rh = _rh;
			look_ahead = _look_ahead;
		}

		bool operator==(const LRItem& item) const {
			if (lf != item.lf) return false;
			if (look_ahead != item.look_ahead) return false;
			if (rh.size() != item.rh.size()) return false;
			for (int cnt = 0; cnt < rh.size(); ++cnt) {
				if (rh[cnt] != item.rh[cnt]) {
					return false;
				}
			}
			return true;
		}
	};
 
	class LRItemHash {
	public:
		size_t operator()(const LRItem& item) const {
			auto res = std::hash<std::string>()(item.lf);
			res ^= std::hash<std::string>()(item.look_ahead);
			for (int cnt = 0; cnt < item.rh.size(); ++cnt) {
				res ^= std::hash<std::string>()(item.rh[cnt]);
			}
			return res;
		}
	
	};
	typedef std::unordered_set<LR::LRItem, LR::LRItemHash> LRItems;
	std::deque<LRItems> items_que;												// 各项目集按顺序存储

	LRItems init_item(); 														// 初始LR1项目集
	void get_lf_appears();														// 得出符号出现在哪些产生式左侧
	void print_lf_appears();
	std::unordered_set<std::string> first_of_list(std::vector<std::string> &);					
	void closure(LRItems &, LRItems &);
	void go_to(LRItems &, std::string, LRItems &);
	void build_predict();														// 构建预测分析表
	void print_predict(int);													// 打印
	std::vector<std::string> analyse_tokens(std::vector<Token>&);

};

class LL: public Syn {
protected:
	std::unordered_map<std::string, std::unordered_map<std::string, int>> predict; // LL预测分析表

public:
	std::unordered_set<std::string> first_of_seq(std::vector<std::string> &);
	void build_predict();						// 构建预测分析表
	void print_predict();						// 打印
	std::vector<std::string> analyse_tokens(std::vector<Token> &);
};
